#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <sys/time.h>
#include <math.h>
#include <cstdlib>
#include <ctime>
#include <sys/timeb.h>
#include <list>
#include <utility>
#include <stack>
#include <fstream>
#include <vector>
using namespace std;


struct pueblo{
        int id;
        int posX;
        int posY;
};

struct arista{
	int idNodo1;
	int idNodo2;
	double longitud;
};




void merge(arista*,arista*,int,int,int);
void mergesort(arista *a, arista*b, int low, int high)
{

	int pivot;
    if(low<high)
    {
		pivot=(low+high)/2;
        mergesort(a,b,low,pivot);
        mergesort(a,b,pivot+1,high);
        merge(a,b,low,pivot,high);
    }
}
void merge(arista *a,arista *b, int low, int pivot, int high)
{
    int k;
    int h=low;
    int i=low;
    int j=pivot+1;
    while((h<=pivot)&&(j<=high))
    {
        if( a[h].longitud > a[j].longitud  )
        {
            b[i]=a[h];
            h++;
        }else{
            b[i]=a[j];
            j++;
        }
        i++;
    }
    if(h>pivot)
    {
        for(k=j; k<=high; k++)
        {
            b[i]=a[k];
            i++;
        }
    }else{
        for(k=h; k<=pivot; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    for(k=low; k<=high; k++) {
                a[k]=b[k];
    }
}


void tratarLinea(string line, string& first,string& second){
		vector<string> entradaSplit;
		int fromIndex = 0;
		int length = 0;
		for(int i=0; i<line.length(); i++) {
			if(i == line.length() - 1) {
				length++;
				entradaSplit.push_back(line.substr(fromIndex, length));
			} else if(line[i] == ' ') {
				entradaSplit.push_back(line.substr(fromIndex, length));
				fromIndex = i+1;
				length = 0;
			} else {
				length++;
			}
		}
		first = entradaSplit[0].c_str();
		second = entradaSplit[1].c_str();

}

double distancia(pueblo p1, pueblo p2){

	return sqrt(pow(p2.posX - p1.posX,2) + pow(p2.posY- p1.posY,2));

}


pair<pueblo*,arista*> ubicarCentrales(pueblo* pueblos,int cantPueblos, int cantCentrales ,stack<int> nodosRecorridos,int& tuberiasConstruidas){

    vector< vector<double> > nodosXdist (cantPueblos);
    for(int i = 0;i<cantPueblos;i++){
        nodosXdist[i].resize(cantPueblos);
    }

//Matriz de distancias

	for(int i = 0; i< cantPueblos;i++){
		for(int j=0;j<cantPueblos;j++){
			nodosXdist[i][j] = (double) 0;
		}
	}

	for(int i = 0; i< cantPueblos;i++){
		for(int j=0;j<cantPueblos;j++){
			nodosXdist[i][j] = distancia(pueblos[i],pueblos[j]);
		}
	}

	//Comienzo algoritmo PRIM
	int ultimaPosArista = 0;
	int* masProximo = new int[cantPueblos];
	double* distMin = new double[cantPueblos];
	arista* aristas = new arista[cantPueblos-1];
	//Armo mi arreglo de distancias minimas con el nodo 0 que es el elegido para empezar
	for(int i = 0; i<cantPueblos;i++){
		masProximo[i] = 0;
		distMin[i] = nodosXdist[i][0];
	}

	int nodoActual = 0;
	int cantIteraciones = cantPueblos-1;
	//bucle voraz
	distMin[0]=-1;
	while(cantIteraciones>0){
		//Marco el tamaño de mi minimo
		double min = -1;
		//Busco el minimo en mi arreglo de distancias
		for(int i = 0;i< cantPueblos;i++){
				if(min == -1 || (min !=-1 && 0 < distMin[i] && distMin[i]< min)){
					min = distMin[i];
					nodoActual = i;
				}
		}

		//Se añade la arista a la lista con el elemento que mas cerca este
		arista nuevaTuberia = {masProximo[nodoActual],nodoActual,distMin[nodoActual]};
		aristas[ultimaPosArista] = nuevaTuberia;
		ultimaPosArista++;

		//Se marca como que ya esta agregado
		distMin[nodoActual]=-1;

		//actualizo mi arreglo de distancias minimas en base a mi nuevo
		//nodo comparando con los anteriores
		for(int i = 0;i<cantPueblos;i++)
		{
			if(nodosXdist[i][nodoActual]< distMin[i]){
				distMin[i] = nodosXdist[i][nodoActual];
				masProximo[i] = nodoActual;
			}
		}
		cantIteraciones--;
	}


	//Ordeno las aristas
	arista* aux =  new arista[cantPueblos-2];
	mergesort(aristas,aux,0,cantPueblos-3);

	//Armo la matriz de adyacencias, 1 si es un nodo conectado 0 caso contrario
	vector< vector<int> > adyacencias(cantPueblos); //O(n^2)
    for(int i=0;i<cantPueblos;i++)
        adyacencias[i].resize(cantPueblos);

	//La lleno de ceros al principio ninguno esta conectado
	for(int i = 0 ; i < cantPueblos ; i++){
			for(int j =0;j<cantPueblos;j++){
					adyacencias[i][j]= 0;
			}
	}
//Arranco a completar desde la cantidad de centrales que tengo para colocar
//Esto es lo mismo que sacar las k-1 aristas mas grandes para colocar centrales

	for(int i = cantCentrales-1; i < cantPueblos-1; i++){
		adyacencias[aristas[i].idNodo1][aristas[i].idNodo2] = 1;
		adyacencias[aristas[i].idNodo2][aristas[i].idNodo1] = 1;
	}


	//Armo la salida, lista de pueblos donde va una central
	bool* conectadoAcentral = new bool[cantPueblos];
	for(int i = 0; i<cantPueblos; i++){
		conectadoAcentral[i] =false;
	}

	pueblo* centrales = new pueblo[cantCentrales];
	int centralActual = 0;
	//Recorro la matriz de adyacencias para ir colocando las centrales segun el arreglo auxiliar que me indica si ya esta conectado auna central o no
	//Cuando no esta conectado a una central se convierte en central, actualizo el arreglo auxiliar marcando a todas sus adyacencias como conectados a una central.

	bool* recorridos = new bool[cantPueblos];
	for(int i = 0; i<cantPueblos; i++){
			recorridos[i] = false;
	}


	nodosRecorridos.push(0); //Pusheo el numero del pueblo 0
	recorridos[0]=true; //Lo marco como recorrido

	while(!nodosRecorridos.empty()){

		int actual = nodosRecorridos.top();//Me guardo el tope del stack

		nodosRecorridos.pop();//Saco el nodo que voy a recorrer

		for(int i =0;i<cantPueblos;i++){
			if(adyacencias[actual][i] == 1 && !recorridos[i]){
					nodosRecorridos.push(i);
					recorridos[i] = true; //Evito recorrerlo 2 veces
			}
		}

		if(nodosRecorridos.empty()){
			//estoy en el ultimo nodo del grafo y lo guardo para colocar la central
			centrales[centralActual] = pueblos[actual];
			centralActual++;

			int proximo = 0;
			bool encontreProximo = false;
			//Busco el proximo nodo de otro grafo conexo para recorrer

			while(!encontreProximo && proximo < cantPueblos){
					if(!recorridos[proximo]){
						actual = proximo;
						nodosRecorridos.push(proximo);
						encontreProximo = true;
						recorridos[proximo]=true;
					}else{
						proximo++;
					}
			}
		}
	}
    arista* tuberias;
    if(cantPueblos>cantCentrales){
        tuberias = new arista[cantPueblos-cantCentrales+1];
        //ARMO LA SALIDA, las aristas sacando las k-1 mas grandes
        int j = 0;
        for(int i = cantCentrales-1;i<cantPueblos;i++){
                    tuberias[j] = aristas[i];
                    j++;
        }
        tuberiasConstruidas = j-1;
	}
/*
	for(int i = 0; i< cantPueblos;i++){
		delete []adyacencias[i];
	}
	delete adyacencias;
	for(int i = 0; i< cantPueblos;i++){
		delete []nodosXdist[i];
	}*/


	delete aux;
	delete recorridos;

	delete conectadoAcentral;
	delete distMin;
	delete masProximo;


	pair <pueblo*,arista* > resultado = make_pair(centrales,tuberias);
	return resultado;
}


int main(int argc, char *argv[])
{


    string line;
	bool primerLinea = true;
	int cantPueblos, cantCentrales;
	string s_pueblos,s_centrales,s_posx, s_posy ;
	int i = 0;// para evitar leer lineas de mas
	pueblo* pueblos = NULL;

  
	//Comienzo la lectura del archivo
	while ( getline (cin,line) ){
		if(primerLinea){
			tratarLinea(line,s_pueblos,s_centrales);
			cantPueblos = atoi(s_pueblos.c_str());
			cantCentrales = atoi(s_centrales.c_str());
			pueblos = new pueblo[cantPueblos];
			primerLinea=false;
			continue;
		}

		tratarLinea(line,s_posx,s_posy);
		pueblo nuevo = {i,atoi(s_posx.c_str()),atoi(s_posy.c_str())};
		//cout << nuevo.posX + " " + nuevo.posY << endl;
		pueblos[i]=nuevo;
		//cout << nuevo.id << endl;
		i++;
		if(i > cantPueblos-1){
			break;
		}
	}

	

	stack<int> nodosRecorridos ;
	int tuberiasConstruidas = 0;
	pair< pueblo*,arista* > construccion = ubicarCentrales(pueblos,cantPueblos,cantCentrales,nodosRecorridos,tuberiasConstruidas);

	//SALIDA EN EL ARCHIVO
	cout << cantCentrales << " " << tuberiasConstruidas << endl;
	cout << "Lista de centrales" << endl;

	for(int i = 0; i<cantCentrales;i++)
	{
		cout << construccion.first[i].id ;
		cout << " ";
	}
	cout << endl;

	cout << "lista de tuberias" << endl;
	for(int i = 0; i<cantPueblos-cantCentrales;i++)
	{
		cout << i << " ";
		cout << "<";
		cout << construccion.second[i].idNodo1;
		cout << ",";
		cout << construccion.second[i].idNodo2;
		cout << ",";
		cout << construccion.second[i].longitud;
		cout << ">"<< endl;
	}
	delete pueblos;


    return 0;
}
